/*
 * Copyright (C) 2007, 2008 Apple Inc. All rights reserved.
 * Copyright (C) 2009 Google Inc. All rights reserved.
 *
 * Redistribution and use in source and binary forms, with or without
 * modification, are permitted provided that the following conditions
 * are met:
 *
 * 1.  Redistributions of source code must retain the above copyright
 *     notice, this list of conditions and the following disclaimer.
 * 2.  Redistributions in binary form must reproduce the above copyright
 *     notice, this list of conditions and the following disclaimer in the
 *     documentation and/or other materials provided with the distribution.
 * 3.  Neither the name of Apple Computer, Inc. ("Apple") nor the names of
 *     its contributors may be used to endorse or promote products derived
 *     from this software without specific prior written permission.
 *
 * THIS SOFTWARE IS PROVIDED BY APPLE AND ITS CONTRIBUTORS "AS IS" AND ANY
 * EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED
 * WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
 * DISCLAIMED. IN NO EVENT SHALL APPLE OR ITS CONTRIBUTORS BE LIABLE FOR ANY
 * DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES
 * (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
 * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND
 * ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
 * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
 */

#ifndef WTF_Deque_h
#define WTF_Deque_h

// FIXME: Could move what Vector and Deque share into a separate file.
// Deque doesn't actually use Vector.

#include "wtf/Vector.h"
#include <iterator>

namespace WTF {

template <typename T, size_t inlineCapacity, typename Allocator> class DequeIteratorBase;
template <typename T, size_t inlineCapacity, typename Allocator> class DequeIterator;
template <typename T, size_t inlineCapacity, typename Allocator> class DequeConstIterator;

template <typename T, size_t inlineCapacity = 0, typename Allocator = PartitionAllocator>
class Deque : public ConditionalDestructor<Deque<T, INLINE_CAPACITY, Allocator>, (INLINE_CAPACITY == 0) && Allocator::isGarbageCollected> {
    WTF_USE_ALLOCATOR(Deque, Allocator);
public:
    typedef DequeIterator<T, inlineCapacity, Allocator> iterator;
    typedef DequeConstIterator<T, inlineCapacity, Allocator> const_iterator;
    typedef std::reverse_iterator<iterator> reverse_iterator;
    typedef std::reverse_iterator<const_iterator> const_reverse_iterator;

    Deque();
    Deque(const Deque<T, inlineCapacity, Allocator>&);
    // FIXME: Doesn't work if there is an inline buffer, due to crbug.com/360572
    Deque<T, 0, Allocator>& operator=(const Deque&);

    void finalize();
    void finalizeGarbageCollectedObject() { finalize(); }

    // We hard wire the inlineCapacity to zero here, due to crbug.com/360572
    void swap(Deque<T, 0, Allocator>&);

    size_t size() const { return m_start <= m_end ? m_end - m_start : m_end + m_buffer.capacity() - m_start; }
    bool isEmpty() const { return m_start == m_end; }

    iterator begin() { return iterator(this, m_start); }
    iterator end() { return iterator(this, m_end); }
    const_iterator begin() const { return const_iterator(this, m_start); }
    const_iterator end() const { return const_iterator(this, m_end); }
    reverse_iterator rbegin() { return reverse_iterator(end()); }
    reverse_iterator rend() { return reverse_iterator(begin()); }
    const_reverse_iterator rbegin() const { return const_reverse_iterator(end()); }
    const_reverse_iterator rend() const { return const_reverse_iterator(begin()); }

    T& first() { ASSERT(m_start != m_end); return m_buffer.buffer()[m_start]; }
    const T& first() const { ASSERT(m_start != m_end); return m_buffer.buffer()[m_start]; }
    T takeFirst();

    T& last() { ASSERT(m_start != m_end); return *(--end()); }
    const T& last() const { ASSERT(m_start != m_end); return *(--end()); }
    T takeLast();

    T& at(size_t i)
    {
        RELEASE_ASSERT(i < size());
        size_t right = m_buffer.capacity() - m_start;
        return i < right ? m_buffer.buffer()[m_start + i] : m_buffer.buffer()[i - right];
    }
    const T& at(size_t i) const
    {
        RELEASE_ASSERT(i < size());
        size_t right = m_buffer.capacity() - m_start;
        return i < right ? m_buffer.buffer()[m_start + i] : m_buffer.buffer()[i - right];
    }

    T& operator[](size_t i) { return at(i); }
    const T& operator[](size_t i) const { return at(i); }

    template <typename U> void append(U&&);
    template <typename U> void prepend(U&&);
    void removeFirst();
    void removeLast();
    void remove(iterator&);
    void remove(const_iterator&);

    void clear();

    template <typename Predicate>
    iterator findIf(Predicate&);

    template <typename VisitorDispatcher> void trace(VisitorDispatcher);

private:
    friend class DequeIteratorBase<T, inlineCapacity, Allocator>;

    typedef VectorBuffer<T, INLINE_CAPACITY, Allocator> Buffer;
    typedef VectorTypeOperations<T> TypeOperations;
    typedef DequeIteratorBase<T, inlineCapacity, Allocator> IteratorBase;

    void remove(size_t position);
    void destroyAll();
    void expandCapacityIfNeeded();
    void expandCapacity();

    Buffer m_buffer;
    unsigned m_start;
    unsigned m_end;
};

template <typename T, size_t inlineCapacity, typename Allocator>
class DequeIteratorBase {
protected:
    DequeIteratorBase();
    DequeIteratorBase(const Deque<T, inlineCapacity, Allocator>*, size_t);
    DequeIteratorBase(const DequeIteratorBase&);
    DequeIteratorBase<T, 0, Allocator>& operator=(const DequeIteratorBase<T, 0, Allocator>&);
    ~DequeIteratorBase();

    void assign(const DequeIteratorBase& other) { *this = other; }

    void increment();
    void decrement();

    T* before() const;
    T* after() const;

    bool isEqual(const DequeIteratorBase&) const;

private:
    Deque<T, inlineCapacity, Allocator>* m_deque;
    unsigned m_index;

    friend class Deque<T, inlineCapacity, Allocator>;
};

template <typename T, size_t inlineCapacity = 0, typename Allocator = PartitionAllocator>
class DequeIterator : public DequeIteratorBase<T, inlineCapacity, Allocator> {
private:
    typedef DequeIteratorBase<T, inlineCapacity, Allocator> Base;
    typedef DequeIterator<T, inlineCapacity, Allocator> Iterator;

public:
    typedef ptrdiff_t difference_type;
    typedef T value_type;
    typedef T* pointer;
    typedef T& reference;
    typedef std::bidirectional_iterator_tag iterator_category;

    DequeIterator(Deque<T, inlineCapacity, Allocator>* deque, size_t index) : Base(deque, index) {}

    DequeIterator(const Iterator& other) : Base(other) {}
    DequeIterator& operator=(const Iterator& other) { Base::assign(other); return *this; }

    T& operator*() const { return *Base::after(); }
    T* operator->() const { return Base::after(); }

    bool operator==(const Iterator& other) const { return Base::isEqual(other); }
    bool operator!=(const Iterator& other) const { return !Base::isEqual(other); }

    Iterator& operator++() { Base::increment(); return *this; }
    // postfix ++ intentionally omitted
    Iterator& operator--() { Base::decrement(); return *this; }
    // postfix -- intentionally omitted
};

template <typename T, size_t inlineCapacity = 0, typename Allocator = PartitionAllocator>
class DequeConstIterator : public DequeIteratorBase<T, inlineCapacity, Allocator> {
private:
    typedef DequeIteratorBase<T, inlineCapacity, Allocator> Base;
    typedef DequeConstIterator<T, inlineCapacity, Allocator> Iterator;
    typedef DequeIterator<T, inlineCapacity, Allocator> NonConstIterator;

public:
    typedef ptrdiff_t difference_type;
    typedef T value_type;
    typedef const T* pointer;
    typedef const T& reference;
    typedef std::bidirectional_iterator_tag iterator_category;

    DequeConstIterator(const Deque<T, inlineCapacity, Allocator>* deque, size_t index) : Base(deque, index) {}

    DequeConstIterator(const Iterator& other) : Base(other) {}
    DequeConstIterator(const NonConstIterator& other) : Base(other) {}
    DequeConstIterator& operator=(const Iterator& other) { Base::assign(other); return *this; }
    DequeConstIterator& operator=(const NonConstIterator& other) { Base::assign(other); return *this; }

    const T& operator*() const { return *Base::after(); }
    const T* operator->() const { return Base::after(); }

    bool operator==(const Iterator& other) const { return Base::isEqual(other); }
    bool operator!=(const Iterator& other) const { return !Base::isEqual(other); }

    Iterator& operator++() { Base::increment(); return *this; }
    // postfix ++ intentionally omitted
    Iterator& operator--() { Base::decrement(); return *this; }
    // postfix -- intentionally omitted
};

template <typename T, size_t inlineCapacity, typename Allocator>
inline Deque<T, inlineCapacity, Allocator>::Deque()
    : m_start(0)
    , m_end(0)
{
    static_assert(!std::is_polymorphic<T>::value || !VectorTraits<T>::canInitializeWithMemset, "Cannot initialize with memset if there is a vtable");
#if ENABLE(OILPAN)
    static_assert(Allocator::isGarbageCollected || !AllowsOnlyPlacementNew<T>::value || !NeedsTracing<T>::value, "Cannot put DISALLOW_NEW_EXCEPT_PLACEMENT_NEW objects that have trace methods into an off-heap Deque");
#endif
    static_assert(Allocator::isGarbageCollected || !IsPointerToGarbageCollectedType<T>::value, "Cannot put raw pointers to garbage-collected classes into a Deque. Use HeapDeque<Member<T>> instead.");
}

template <typename T, size_t inlineCapacity, typename Allocator>
inline Deque<T, inlineCapacity, Allocator>::Deque(const Deque<T, inlineCapacity, Allocator>& other)
    : m_buffer(other.m_buffer.capacity())
    , m_start(other.m_start)
    , m_end(other.m_end)
{
    const T* otherBuffer = other.m_buffer.buffer();
    if (m_start <= m_end) {
        TypeOperations::uninitializedCopy(otherBuffer + m_start, otherBuffer + m_end, m_buffer.buffer() + m_start);
    } else {
        TypeOperations::uninitializedCopy(otherBuffer, otherBuffer + m_end, m_buffer.buffer());
        TypeOperations::uninitializedCopy(otherBuffer + m_start, otherBuffer + m_buffer.capacity(), m_buffer.buffer() + m_start);
    }
}

template <typename T, size_t inlineCapacity, typename Allocator>
inline Deque<T, 0, Allocator>& Deque<T, inlineCapacity, Allocator>::operator=(const Deque& other)
{
    Deque<T> copy(other);
    swap(copy);
    return *this;
}

template <typename T, size_t inlineCapacity, typename Allocator>
inline void Deque<T, inlineCapacity, Allocator>::destroyAll()
{
    if (m_start <= m_end) {
        TypeOperations::destruct(m_buffer.buffer() + m_start, m_buffer.buffer() + m_end);
        m_buffer.clearUnusedSlots(m_buffer.buffer() + m_start, m_buffer.buffer() + m_end);
    } else {
        TypeOperations::destruct(m_buffer.buffer(), m_buffer.buffer() + m_end);
        m_buffer.clearUnusedSlots(m_buffer.buffer(), m_buffer.buffer() + m_end);
        TypeOperations::destruct(m_buffer.buffer() + m_start, m_buffer.buffer() + m_buffer.capacity());
        m_buffer.clearUnusedSlots(m_buffer.buffer() + m_start, m_buffer.buffer() + m_buffer.capacity());
    }
}

// Off-GC-heap deques: Destructor should be called.
// On-GC-heap deques: Destructor should be called for inline buffers (if any)
// but destructor shouldn't be called for vector backing since it is managed by
// the traced GC heap.
template <typename T, size_t inlineCapacity, typename Allocator>
inline void Deque<T, inlineCapacity, Allocator>::finalize()
{
    if (!INLINE_CAPACITY && !m_buffer.buffer())
        return;
    if (!isEmpty() && !(Allocator::isGarbageCollected && m_buffer.hasOutOfLineBuffer()))
        destroyAll();

    m_buffer.destruct();
}

// FIXME: Doesn't work if there is an inline buffer, due to crbug.com/360572
template <typename T, size_t inlineCapacity, typename Allocator>
inline void Deque<T, inlineCapacity, Allocator>::swap(Deque<T, 0, Allocator>& other)
{
    std::swap(m_start, other.m_start);
    std::swap(m_end, other.m_end);
    m_buffer.swapVectorBuffer(other.m_buffer);
}

template <typename T, size_t inlineCapacity, typename Allocator>
inline void Deque<T, inlineCapacity, Allocator>::clear()
{
    destroyAll();
    m_start = 0;
    m_end = 0;
    m_buffer.deallocateBuffer(m_buffer.buffer());
    m_buffer.resetBufferPointer();
}

template <typename T, size_t inlineCapacity, typename Allocator>
template <typename Predicate>
inline DequeIterator<T, inlineCapacity, Allocator> Deque<T, inlineCapacity, Allocator>::findIf(Predicate& predicate)
{
    iterator endIterator = end();
    for (iterator it = begin(); it != endIterator; ++it) {
        if (predicate(*it))
            return it;
    }
    return endIterator;
}

template <typename T, size_t inlineCapacity, typename Allocator>
inline void Deque<T, inlineCapacity, Allocator>::expandCapacityIfNeeded()
{
    if (m_start) {
        if (m_end + 1 != m_start)
            return;
    } else if (m_end) {
        if (m_end != m_buffer.capacity() - 1)
            return;
    } else if (m_buffer.capacity()) {
        return;
    }

    expandCapacity();
}

template <typename T, size_t inlineCapacity, typename Allocator>
void Deque<T, inlineCapacity, Allocator>::expandCapacity()
{
    size_t oldCapacity = m_buffer.capacity();
    T* oldBuffer = m_buffer.buffer();
    size_t newCapacity = std::max(static_cast<size_t>(16), oldCapacity + oldCapacity / 4 + 1);
    if (m_buffer.expandBuffer(newCapacity)) {
        if (m_start <= m_end) {
            // No adjustments to be done.
        } else {
            size_t newStart = m_buffer.capacity() - (oldCapacity - m_start);
            TypeOperations::moveOverlapping(oldBuffer + m_start, oldBuffer + oldCapacity, m_buffer.buffer() + newStart);
            m_buffer.clearUnusedSlots(oldBuffer + m_start, oldBuffer + std::min(oldCapacity, newStart));
            m_start = newStart;
        }
        return;
    }
    m_buffer.allocateBuffer(newCapacity);
    if (m_start <= m_end) {
        TypeOperations::move(oldBuffer + m_start, oldBuffer + m_end, m_buffer.buffer() + m_start);
        m_buffer.clearUnusedSlots(oldBuffer + m_start, oldBuffer + m_end);
    } else {
        TypeOperations::move(oldBuffer, oldBuffer + m_end, m_buffer.buffer());
        m_buffer.clearUnusedSlots(oldBuffer, oldBuffer + m_end);
        size_t newStart = m_buffer.capacity() - (oldCapacity - m_start);
        TypeOperations::move(oldBuffer + m_start, oldBuffer + oldCapacity, m_buffer.buffer() + newStart);
        m_buffer.clearUnusedSlots(oldBuffer + m_start, oldBuffer + oldCapacity);
        m_start = newStart;
    }
    m_buffer.deallocateBuffer(oldBuffer);
}

template <typename T, size_t inlineCapacity, typename Allocator>
inline T Deque<T, inlineCapacity, Allocator>::takeFirst()
{
    T oldFirst = std::move(first());
    removeFirst();
    return oldFirst;
}

template <typename T, size_t inlineCapacity, typename Allocator>
inline T Deque<T, inlineCapacity, Allocator>::takeLast()
{
    T oldLast = std::move(last());
    removeLast();
    return oldLast;
}

template <typename T, size_t inlineCapacity, typename Allocator>
template <typename U>
inline void Deque<T, inlineCapacity, Allocator>::append(U&& value)
{
    expandCapacityIfNeeded();
    new (NotNull, &m_buffer.buffer()[m_end]) T(std::forward<U>(value));
    if (m_end == m_buffer.capacity() - 1)
        m_end = 0;
    else
        ++m_end;
}

template <typename T, size_t inlineCapacity, typename Allocator>
template <typename U>
inline void Deque<T, inlineCapacity, Allocator>::prepend(U&& value)
{
    expandCapacityIfNeeded();
    if (!m_start)
        m_start = m_buffer.capacity() - 1;
    else
        --m_start;
    new (NotNull, &m_buffer.buffer()[m_start]) T(std::forward<U>(value));
}

template <typename T, size_t inlineCapacity, typename Allocator>
inline void Deque<T, inlineCapacity, Allocator>::removeFirst()
{
    ASSERT(!isEmpty());
    TypeOperations::destruct(&m_buffer.buffer()[m_start], &m_buffer.buffer()[m_start + 1]);
    m_buffer.clearUnusedSlots(&m_buffer.buffer()[m_start], &m_buffer.buffer()[m_start + 1]);
    if (m_start == m_buffer.capacity() - 1)
        m_start = 0;
    else
        ++m_start;
}

template <typename T, size_t inlineCapacity, typename Allocator>
inline void Deque<T, inlineCapacity, Allocator>::removeLast()
{
    ASSERT(!isEmpty());
    if (!m_end)
        m_end = m_buffer.capacity() - 1;
    else
        --m_end;
    TypeOperations::destruct(&m_buffer.buffer()[m_end], &m_buffer.buffer()[m_end + 1]);
    m_buffer.clearUnusedSlots(&m_buffer.buffer()[m_end], &m_buffer.buffer()[m_end + 1]);
}

template <typename T, size_t inlineCapacity, typename Allocator>
inline void Deque<T, inlineCapacity, Allocator>::remove(iterator& it)
{
    remove(it.m_index);
}

template <typename T, size_t inlineCapacity, typename Allocator>
inline void Deque<T, inlineCapacity, Allocator>::remove(const_iterator& it)
{
    remove(it.m_index);
}

template <typename T, size_t inlineCapacity, typename Allocator>
inline void Deque<T, inlineCapacity, Allocator>::remove(size_t position)
{
    if (position == m_end)
        return;

    T* buffer = m_buffer.buffer();
    TypeOperations::destruct(&buffer[position], &buffer[position + 1]);

    // Find which segment of the circular buffer contained the remove element,
    // and only move elements in that part.
    if (position >= m_start) {
        TypeOperations::moveOverlapping(buffer + m_start, buffer + position, buffer + m_start + 1);
        m_buffer.clearUnusedSlots(buffer + m_start, buffer + m_start + 1);
        m_start = (m_start + 1) % m_buffer.capacity();
    } else {
        TypeOperations::moveOverlapping(buffer + position + 1, buffer + m_end, buffer + position);
        m_buffer.clearUnusedSlots(buffer + m_end - 1, buffer + m_end);
        m_end = (m_end - 1 + m_buffer.capacity()) % m_buffer.capacity();
    }
}

template <typename T, size_t inlineCapacity, typename Allocator>
inline DequeIteratorBase<T, inlineCapacity, Allocator>::DequeIteratorBase()
    : m_deque(0)
{
}

template <typename T, size_t inlineCapacity, typename Allocator>
inline DequeIteratorBase<T, inlineCapacity, Allocator>::DequeIteratorBase(const Deque<T, inlineCapacity, Allocator>* deque, size_t index)
    : m_deque(const_cast<Deque<T, inlineCapacity, Allocator>*>(deque))
    , m_index(index)
{
}

template <typename T, size_t inlineCapacity, typename Allocator>
inline DequeIteratorBase<T, inlineCapacity, Allocator>::DequeIteratorBase(const DequeIteratorBase& other)
    : m_deque(other.m_deque)
    , m_index(other.m_index)
{
}

template <typename T, size_t inlineCapacity, typename Allocator>
inline DequeIteratorBase<T, 0, Allocator>& DequeIteratorBase<T, inlineCapacity, Allocator>::operator=(const DequeIteratorBase<T, 0, Allocator>& other)
{
    m_deque = other.m_deque;
    m_index = other.m_index;
    return *this;
}

template <typename T, size_t inlineCapacity, typename Allocator>
inline DequeIteratorBase<T, inlineCapacity, Allocator>::~DequeIteratorBase()
{
}

template <typename T, size_t inlineCapacity, typename Allocator>
inline bool DequeIteratorBase<T, inlineCapacity, Allocator>::isEqual(const DequeIteratorBase& other) const
{
    return m_index == other.m_index;
}

template <typename T, size_t inlineCapacity, typename Allocator>
inline void DequeIteratorBase<T, inlineCapacity, Allocator>::increment()
{
    ASSERT(m_index != m_deque->m_end);
    ASSERT(m_deque->m_buffer.capacity());
    if (m_index == m_deque->m_buffer.capacity() - 1)
        m_index = 0;
    else
        ++m_index;
}

template <typename T, size_t inlineCapacity, typename Allocator>
inline void DequeIteratorBase<T, inlineCapacity, Allocator>::decrement()
{
    ASSERT(m_index != m_deque->m_start);
    ASSERT(m_deque->m_buffer.capacity());
    if (!m_index)
        m_index = m_deque->m_buffer.capacity() - 1;
    else
        --m_index;
}

template <typename T, size_t inlineCapacity, typename Allocator>
inline T* DequeIteratorBase<T, inlineCapacity, Allocator>::after() const
{
    ASSERT(m_index != m_deque->m_end);
    return &m_deque->m_buffer.buffer()[m_index];
}

template <typename T, size_t inlineCapacity, typename Allocator>
inline T* DequeIteratorBase<T, inlineCapacity, Allocator>::before() const
{
    ASSERT(m_index != m_deque->m_start);
    if (!m_index)
        return &m_deque->m_buffer.buffer()[m_deque->m_buffer.capacity() - 1];
    return &m_deque->m_buffer.buffer()[m_index - 1];
}

// This is only called if the allocator is a HeapAllocator. It is used when
// visiting during a tracing GC.
template <typename T, size_t inlineCapacity, typename Allocator>
template <typename VisitorDispatcher>
void Deque<T, inlineCapacity, Allocator>::trace(VisitorDispatcher visitor)
{
    ASSERT(Allocator::isGarbageCollected); // Garbage collector must be enabled.
    const T* bufferBegin = m_buffer.buffer();
    const T* end = bufferBegin + m_end;
    if (NeedsTracingTrait<VectorTraits<T>>::value) {
        if (m_start <= m_end) {
            for (const T* bufferEntry = bufferBegin + m_start; bufferEntry != end; bufferEntry++)
                Allocator::template trace<VisitorDispatcher, T, VectorTraits<T>>(visitor, *const_cast<T*>(bufferEntry));
        } else {
            for (const T* bufferEntry = bufferBegin; bufferEntry != end; bufferEntry++)
                Allocator::template trace<VisitorDispatcher, T, VectorTraits<T>>(visitor, *const_cast<T*>(bufferEntry));
            const T* bufferEnd = m_buffer.buffer() + m_buffer.capacity();
            for (const T* bufferEntry = bufferBegin + m_start; bufferEntry != bufferEnd; bufferEntry++)
                Allocator::template trace<VisitorDispatcher, T, VectorTraits<T>>(visitor, *const_cast<T*>(bufferEntry));
        }
    }
    if (m_buffer.hasOutOfLineBuffer())
        Allocator::markNoTracing(visitor, m_buffer.buffer());
}

template <typename T, size_t inlineCapacity, typename Allocator>
inline void swap(Deque<T, inlineCapacity, Allocator>& a, Deque<T, inlineCapacity, Allocator>& b)
{
    a.swap(b);
}

#if !ENABLE(OILPAN)
template <typename T, size_t N>
struct NeedsTracing<Deque<T, N>> {
    static const bool value = false;
};
#endif

} // namespace WTF

using WTF::Deque;

#endif // WTF_Deque_h
